1. Field of the Invention
The present invention relates to electronic information processing systems, and in particular, to apparatus and methods for controlling access to resources in a multiprocessor environment.
2. Description of Related Art
Electronic information processing system hardware and operating system software designs require a means for ensuring the integrity of accesses to resources such as memory storage locations, external storage, and input or output devices. Resource conflicts may arise when several tasks attempt to access and change a resource. Single processor configurations manage resource conflicts using the inherent property that only a single instruction stream is executing with known points of control transfer. In the single processor case, operating system or application instructions can effectively manage resource control to maintain resource integrity. Multiprocessor systems introduce additional complexity because the contents of a single instruction stream no longer determine the overall access to resources.
Resource conflicts arise in a multiprocessor system when two or more processors attempt to control a single resource. Resource conflicts historically have been resolved by implementing mechanisms to serialize access to the resources. These mechanisms typically implement some form of resource lock allowing only a single processor to have control of a resource during any time period. Access by multiple processors is forced by this mechanism to occur serially rather than in parallel. In addition to the use of different lock forms, techniques for passive serialization exist that do not require locks (see U.S. Pat. No. 4,809,168 "Passive Serialization in a Multitasking Environment", commonly assigned).
Resource locks operate on the assumption that a processor will acquire the lock, perform the instruction and release the lock so that the resource is available for another processor. An instruction with a requirement to simultaneously access more than one resource can potentially lead to a deadlock situation if two processors are waiting for each other to release a needed lock. The first processor may be unable to complete task processing until it acquires a second resource held by a second processor which may be unable to complete its task processing until it acquires the resource held by the first processor. A deadlock of this nature typically requires the computer system to be restarted, an undesirable event in most large scale computer processing environments.
The multiprocessor deadlock potential has resulted in software and hardware designed to avoid requiring simultaneous access to more than one resource. The alternative is to implement a serialization mechanism that locks an entire class or several classes of resources to a single processor. For example, if memory storage representing a particular queue may be subject to multiple resource requests, access to the entire queue can be serialized through the use of a queue lock. The locking of large resource blocks is undesirable, however, when implementing basic operating system functions such as task scheduling or other time dependent queueing. The creation of a lock on the entire queue reduces throughput by locking and serializing processor access, thereby reducing the overall system processing efficiency.
A second problem of multiprocessor access to multiple resources is a potential loss of resource integrity. Simultaneous access and update of a resource can lead to corrupted data when two processors make conflicting changes to coordinated resources.
Time dependent queues are employed for many operating system functions where time dependent lists are required. For example, a task list queue containing a "first-in first-out" (FIFO) listing of the next tasks to be processed by a multiprocessor system is an essential work management tool. Allowing only single processor access to the entire list would prevent all other processors from inserting work in the queue and removing work for action until the first processor released the queue. This would increase task management overhead.
Multiprocessor queue design and usage has been optimized to minimize the number of locks that must be placed on operating system queues. As discussed above, serialization and locking are primarily required when multiple processor access to the same resources can create a deadlock situation or loss of resource integrity. Thus, if a queue can be designed so that each processor instruction requires only a single resource, e.g., a single storage location, then the potential of resource conflicts and therefore locking can be minimized.
Locks can be provided in a system in increasing degrees of granularity. A fine grained lock system provides locks on small resource units, e.g., a few hundred bytes of storage. Locking systems with less granularity, large grained, provided locks only at a higher level, e.g., on entire data structures or entire resource units such as a storage queue. A fine grained locking scheme reduces the overhead caused by locks blocking processor action, but increases the likelihood of deadlock if multiple resource units are required to complete a given instruction.
A general queue model allows insertion of an entry at any point in the queue and removal of any entry in the queue. Queues are typically implemented as a singly, or doubly, linked list of addresses in a computer system. Each element of the queue contains the address of the next element. The addition of an element within a list therefore typically requires the update of two addresses in a singly linked list and four in a doubly linked list. In the case where two addresses must be updated, since each occupies a separate storage location, two storage locations must be accessed and updated to accomplish the queue insertion. System integrity and reliability require that these address updates be performed "atomically". That is, the update of both addresses must occur without potential interruption of processing between the updates. It must look as though a single instruction is being performed with the update of two addresses. This is known as an "atomic" instruction since it is one that cannot be further subdivided or interrupted during processing. In a system where each storage location is provided with a lock, multiprocessor update of two storage locations raises a high probability of deadlock or data corruption. The only clear alternative is to serialize access to the entire queue with the performance problems listed above.
Operating systems can overcome some of those restrictions by implementing optimized queues where elements can only be added at the tail, a process that requires only a single address update. The single address update does not have the same deadlock risk and therefore the operating system can allow multiple processors to add elements to the list. Removing an element from the queue, however, still requires multiple address updates and therefore must be restricted to a single processor. Thus, in the implementation, dequeuing must be serialized to a single processor.
The existing technical problem, therefore, is a loss of system efficiency because efficient forms of queuing cannot be implemented due to the risk of machine deadlocks and loss of resource integrity. A system allowing a multiprocessor system to atomically update multiple resources without risk of deadlock is required to enhance queue management.